import java.util.Iterator;

/**
 * Static program that asks the user for a text file for input that
 * contains data for a SimpleGraph. The graph is loaded in and the
 * minimal spanning tree for the graph, with a random vertex chosen
 * as the starting vertex, is found using Prim's Algorithm.
 * 
 * @author Chris Davidson, Michelle Miller, and Agari Nln
 * @version Winter 2012.
 */
public class PrimHeapImplementation {

	/**
	 * The main method that handles execution of the Prim's Algorithm execution.
	 * 
	 * @param args Unused command line arguments
	 * @throws EmptyHeapException If the graph this is called on has no vertices or edges.
	 */
	public static void main(String[] args) throws EmptyHeapException {
		final SimpleGraph graph = getGraph();
		final int numVertices = graph.numVertices();
		final Iterator<Vertex> vertices = (Iterator<Vertex>) graph.vertices();
		final PrimBinaryHeap unknowns = new PrimBinaryHeap(numVertices);
		for (int i = 0; i < numVertices; ++i) {
			final Vertex v = (Vertex) vertices.next();
			final PrimHeapNode node = new PrimHeapNode(v);
			v.setData(new PrimVertexData(node));
			unknowns.insert(node);
		}
		
		PrimHeapNode node = null;
		while (!unknowns.isEmpty()) {
			boolean first = node == null;
			node = unknowns.deleteMin();
			((PrimVertexData) node.getVertex().getData()).setKnown();
			if (first) {
				((PrimVertexData) node.getVertex().getData()).update(0.0, null);
			}
			final Iterator<Edge> edges = (Iterator<Edge>) graph.incidentEdges(node.getVertex());
			while (edges.hasNext()) {
				final Edge edge = (Edge) edges.next();
				final Double edge_weight = (Double) edge.getData();
				final Vertex v1 = node.getVertex();
				final Vertex v2 = graph.opposite(v1, edge);
				final Double current_weight = ((PrimVertexData) v2.getData()).getLabel();
				
				if (edge_weight < current_weight && !((PrimVertexData) v2.getData()).isKnown()) {
					((PrimVertexData) v2.getData()).update(edge_weight, edge);
					unknowns.percolateUp(((PrimVertexData) v2.getData()).getNode().getHeapPosition());
				}
			}
		}
		printResult(graph);
	}

	/**
	 * Prints the minimum spanning tree found when Prim's algorithm was called
	 * on the provided SimpleGraph.
	 * @param graph The SimpleGraph that Prim's Algorithm was run on.
	 */
	private static void printResult(SimpleGraph graph) {
		Double cost = 0.0;
		System.out.println("Edges contained in the minimum spanning tree :");
		final Iterator<Vertex> vertices = (Iterator<Vertex>) graph.vertices();
		while (vertices.hasNext()) {
			final Vertex v = vertices.next();
			final Edge e = ((PrimVertexData) v.getData()).getPath();
			if (e == null) {
				System.out.println("\tVertex " + v.getName() +
						" is the root of the MST");
				
			} else {
				System.out.println("\tVertex " + v.getName() +
						" is the child of vertex " + graph.opposite(v, e).getName() +
						" and has an edge weight of " + e.getData());
				cost += (Double) e.getData();
			}
		}
		System.out.print("Cost of the minimum spanning tree found: " + cost);
		
	}

	/**
	 * Prompts the user for a SimpleGraph data file. Relies on the functions of the
	 * GraphInput class provided.
	 * 
	 * @return The SimpleGraph created from the provided file.
	 */
	private static SimpleGraph getGraph() {
		final SimpleGraph s = new SimpleGraph();
//		GraphInput.LoadSimpleGraph(s);
		GraphInput.LoadSimpleGraph(s, "../PrimImplementation/src/test_graph01.txt");
		//This sample returns correct result!
		return s;
	}

}
